package leetcode.median;

/**
 * ClassName: $647_CountSubstrings
 * Description:
 * date: 2022-02-19 11:10
 *
 * @author liyifan
 */
public class $647_CountSubstrings {
    public int countSubstrings(String s) {
        int res = 0;
        char[] arr = s.toCharArray();
        int len = arr.length;

        for (int i = 0;i < len;i++) {
            for (int j = 0;j <= 1;j++) {
                int left = i;
                int right = i + j;
                while (left >= 0 && right < len && arr[left--] == arr[right++]){
                    res++;
                }
            }
        }

        return res;
    }

    public int countSubstrings2(String s) {
        int res = 0;
        char[] arr = s.toCharArray();
        int len = arr.length;
        boolean[][] dp =  new boolean[len][len];
        for (int i = 0;i < len;i++) dp[i][i] = true;

        for (int j = 0;j < len; j++) {
            for (int i = 0;i <= j;i++) {
                if (arr[i] == arr[j] && (j - i < 2  || dp[i + 1][j - 1])) {
                    dp[i][j] =  true;
                    res++;
                }
            }
        }



        return res;
    }

    public int countSubstrings3(String s) {
        int res = 0;

        int len = s.length();

        for (int center = 0; center <= 2 * len - 1;center++) {
            int left = center / 2;
            int right = left + center % 2;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                res++;
                left--;
                right++;
            }
        }

        return res;
    }
}
